1. Field of the Invention
The present invention relates to a computer system for determining a minimum-cost route from a start location to a target location between which a person travels by walking and using a transportation network, such as a public transportation network.
2. Description of the Related Art
An optimal route is difficult to determine in a complicated traffic network. Further, optimization must be effected in consideration of various factors such as time and cost. Theoretically, a computer can determine an optimal route through calculation performed for all possible combinations. However, when the traffic network becomes complicated, calculation time Increases drastically, even when a high-performance computer is used, so that calculation becomes impossible to complete.
In order to avoid such a problem of calculation becoming impossible to complete, various methods have been proposed. A label determination methodxe2x80x94which is used in a computer to determine a shortest route within a traffic networkxe2x80x94reduces computer processing time and provides a quick solution. The label determination method is sometimes called the Dijkstra method, after its inventor. Japanese Patent Application Laid-Open (kokal) Nos. 10-275296 (Navigation Method and System), 10-253376 (Method and System for Determining a Minimum-Cost Route), and 11-44547 (Method and System for Determining a Minimum-Cost Route) each disclose a method of determining a route in a traffic network by use of the label determination method.
An exemplary system which is represented by means of a network as shown in FIG. 1 will be described. Each of black circles in FIG. 1 corresponds to a specific location and is called a xe2x80x9cnode.xe2x80x9d A line connecting adjacent nodes corresponding to respective locations is called a xe2x80x9clink.xe2x80x9d Mathematically, a set including the nodes and links is called a xe2x80x9cgraph.xe2x80x9d When the links have orientation, the graph is called a xe2x80x9cdirected graph,xe2x80x9d and when the links have no orientation, the graph is called an xe2x80x9cundirected graph.xe2x80x9d FIG. 1 shows an exemplary directed graph. A shortest route problem is a problem of finding a shortest route among routes between a start location node s to a target location node t within a network such as the above-described network.
Here, a shortest route P from node s to node t is represented as follows.
P={s, i, J, . . . , k, t}
In this case, when the route P is divided at a certain node into routes P1 and P2, each of the routes P1 and P2 represents the shortest route within a corresponding set. This is called the principle of optimality. The label determination method is an algorithm for mathematically determining the shortest route by use of the principle. That is, the label determination method starts with an empty set. Each node is labeled with a temporary label, and nodes which constitute the shortest route are determined node-by-node in order to expand a shortest-route subset. Finally, all the nodes are labeled with permanent labels. Thus, the shortest route is determined. The following is an algorithm used for programming computers.
When a set of all nodes present between node s and node t is represented by V, the length of the shortest route from node s to node j is represented by d(j), a set of nodes for the shortest route (hereinafter referred to as a xe2x80x9cshortest route node setxe2x80x9d) is represented by S1, and its complementary set is represented by S2 (=Vxe2x88x92S), the shortest route is determined as follows.
(1) The following initialization is performed.
S1←0 (empty set), S2←V,
d(s)←0, d(i)←∞
Here, i represents a node in the complementary set S2, and X←Y represents an operation of replacing X with Y.
(2) If S1=V, then calculation is ended.
(3) If S1xe2x89xa0V, then
the shortest route length d(i) is selected, and
replacement v←i is effected.
Since the length d(v) represents the length of the shortest route from node s to node v, node v is included in the shortest route node set S1, and is excluded from the complementary set S2.
(4) For each node i which is contained in the complementary set S2 and to which a link extending from node V (outgoing link) reaches next, the following calculation is performed.
dxe2x80x2(i)←d(v)+avi
If d(i) greater than dxe2x80x2(i), then
d(i)←dxe2x80x2(i) and p(i)←v.
Here, avi represents the length of a link from node v to node i, and d(i) and dxe2x80x2(i) each represent the length of a route from the start location s to node i. The value d(i) at this point represents the shortest route length which is formed by nodes within the shortest route node set S1. There is a possibility that the complementary set S2 includes a node that provides a shorter route. However, such a shorter route would be found during repeated calculation.
(5) Processing returns to step (2) above.
When the thus-obtained p(i) is followed in reverse order from the final node t on the basis of p(t), the shortest route from the start node s is obtained. For example, when the above-described algorithm is applied to the example shown in FIG. 1, the following is obtained.
Since s=1 and t=5, node 3 is determined to precede node 5, because p(5)=3; node 2 is determined to precede node 3, because p(3)=2; and node 1 is determined to precede node 2, because p(2)=1, so that the start location s is reached. That is, the shortest route is 1xe2x86x922xe2x86x923xe2x86x925, and the length thereof is 85 (=d(5)). Further, the route (1xe2x86x922xe2x86x924) from node 1 to node 4 also has a short route length d(4).
When determination of the route of FIG. 1 is actually simulated by use of the above-described algorithm, it is found that calculation of the length dxe2x80x2(4) from node 3 to node 4 is not required. That is, the label determination method involves a drastic reduction in the amount of calculation as compared with a case in which the shortest route is calculated through use of all combinations.
The above-described label determination method can be applied to determination of a route from a certain station to a target station within a public transportation network. In this case, the shortest route is determined in consideration of not only distance but also time and fare, which are generally referred to as cost.
The label determination method realizes high-speed processing when performed by use of a computer. Especially, when a start location and a target location are predetermined, the label determination method starts route determination from the start location in order to successively find nodes that minimize cost, and determines the route that reaches the target location with minimum cost. The cost to be considered is time or distance, and therefore, xe2x80x9ctravel timexe2x80x9d or xe2x80x9ctravel distancexe2x80x9d is evaluated.
In many navigation systems manufactured to date, the label determination method is frequently used when route determination is performed with an objective of attaining to minimum cost. Examples of such minimum-cost-route determination include a system for determining a minimum-cost route in a railroad network and a system for determining a minimum-cost route in a road network.
However, no conventional navigation system can determine a route along which a person travels by walking and using a transportation network. For example, a navigation system designed for a railroad network does not take into consideration a station to which a person walks from a start location (a station where the person enters the railroad network, hereinafter called an xe2x80x9centrance stationxe2x80x9d) or how long the person takes to reach a target location from a station where the person exits the railroad network (hereinafter called an xe2x80x9cexit stationxe2x80x9d). Therefore, such a navigation system starts route determination after a person designates the station closest to the start location and the station closet to the target location. Therefore, the navigation system cannot guarantee that the determined route including sections in which the person walks minimizes cost, although the system can properly determine a minimum-cost route from the entrance station to the exit station, both designated by the person.
In view of the foregoing, an object of the present invention is to provide a system which is suitable for cases in which a person walks to an entrance station of a transportation network to be used and walks again from an exit station to a target location and which, upon the person designating the target location, can determine a minimum-cost route including sections along which the person walks.
In order to achieve the above object, the present invention provides a method of determining, by use of a computer, a minimum-cost route from a start location to a target location within a traffic network in accordance with a label determination method, in which traffic network locations are represented as nodes and a route between adjacent nodes is represented as a link. The method comprises:
(1) choosing at least one entrance station of a transportation network to be used whose straight-line distance as measured from the start location falls within a predetermined range and at least one exit station of the transportation network whose straight-line distance as measured from the target location falls within the predetermined range, and estimating cost of a walking route from the start location to the entrance station and cost of a walking route from the exit station to the target location, on the basis of the respective straight-line distances, each calculated by use of latitude/longitude data; and
(2) incorporating, as links, the walking routes having estimated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method.
Further, there may be employed the following method which differs from the above-described method in the manner of determining a walking route.
The Method Comprises:
(1) calculating cost of a walking route from the start location to at least one entrance station of a transportation network to be used and cost of a walking route from at least one exit station of the transportation network to the target location, the cost involved in each of the walking routes falling within a designated cost range, and the walking routes being determined by a label determination method which utilizes a road network created from map data including latitude/longitude information and which determines the walking routes under desired cost conditions; and
(2) incorporating, as links, the walking routes having calculated costs into a traffic network comprising the transportation network in order to express a comprehensive traffic network to thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method.
Next, a first aspect of the invention will be described. A computer is operated in order to determine a minimum-cost route from a start location to a target location between which a person walks from the start location to an entrance point (a station in the case of a railroad network) of a transportation network, uses the transportation network to an exit point (a station in the case of a railroad network) of the transportation network, and walks from the exit point of the transportation network to the target location.
First, Overall Processing will be Described.
(1) At least one entrance station of a transportation network to be used whose straight-line distance as measured from the start location falls within a predetermined range and at least one exit station of the transportation network whose straight-line distance as measured from the target location falls within the predetermined range are chosen. Cost of a walking route from the start location to the entrance station and cost of a walking route from the exit station to the target location are estimated on the basis of the straight-line distance between the start location and the entrance station and the straight-line distance between the exit station and the target location, respectively. The walking routes having estimated costs are incorporated, as links, into a traffic network comprising the transportation network. The above-described calculation will be referred to as a xe2x80x9cstraight-line-distance-basis walking cost calculation.xe2x80x9d
(2) The traffic network is expressed, such that locations are represented as nodes, and a route between adjacent nodes is represented as a link. There is introduced a label consisting of the name of a link connecting the start node and a specific node and a cumulative cost from the start node to the specific node. During initial value setting, the start node is labeled with a temporary label (*, 0), and each of the remaining nodes is labeled with a temporary label ("PHgr", ∞), where xe2x80x9c*xe2x80x9d means that no link reaches the start node, xe2x80x9c"PHgr"xe2x80x9d means that no link has yet reached the corresponding node, and xe2x80x9c∞xe2x80x9d means a numerical value which is sufficiently large within the context of a relevant problem.
(3) Among nodes bearing temporary labels, a node having the lowest potential (i.e., cumulative cost) is selected. When the selected node is the target location, the route determination is ended, and the end processing routine described in (5) below is performed. When the selected node is not the target location, the processing routine described in (4) is performed successively.
(4) The potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated. When the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential indicated by the temporary label of the end node is replaced with the calculated potential of the end node. The temporary label of the node having the lowest potential is rendered permanent, and the processing routine described in (3) above is executed.
(5) Permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
Next, xe2x80x9cstraight-line-distance-basis walking cost calculationxe2x80x9d for estimating walking cost on the basis of straight-line distance will be described. The straight-line distance from the start location to an entrance point of a transportation network to be used and the straight-line distance from an exit point of the transportation network to the target location are calculated by use of the following equations.
cos "xgr"=sin xcfx861xc2x7sin xcfx862+cos xcfx861xc2x7cos xcfx862xc2x7(cos(xcex1xe2x88x92xcex2)xe2x80x83xe2x80x83(1)
S=Rxc2x7"xgr"xe2x80x83xe2x80x83(2)
Here, S is a straight-line distance between two locations A and B; R is a radius of curvature of the earth in the vicinity of Japan (approximately 6370 km); "xgr" is an angle between a line extending from the center of an arc A B to the location A and a line extending from the center to the location B; xcex1 and xcfx861 are the latitude and longitude, respectively, of the location A; and xcex2 and xcfx862 are the latitude and longitude, respectively of the location B. The latitude and longitude of each location can be obtained from map data containing latitude/longitude information. The latitude and longitude of the present location can be obtained by use of a GPS receiver. Means such as a GPS receiver is especially effective when the start location is unknown to the person, because the person is walking in an unfamiliar area. In the present invention, the walking distance between the location A and B is treated as being proportional to the straight-line distance therebetween. Therefore, when cost is time, each of a required time from the start location to the closest entrance point of the transportation network and a required time from the exit point of the transportation network to the target location can be calculated through division of the corresponding straight-line distance by an average walking speed. The thus-obtained cost is incorporated in the traffic network to be used.
A maximum cost is designated in advance in relation to the required time from the start location to an entrance point of the transportation network and the required time from an exit point of the transportation network to the target location, and an entrance point(s) and an exit point(s) of the transportation network are selected such that the walking cost does not exceed the maximum cost. When a plurality of entrance points or exit points are selected, a plurality of links are formed between the start location to the respective entrance points of the transportation network and/or between the exit points of the transportation network and the target location.
After the links in the walking sections are incorporated into the traffic network, the following route determination processing is performed for the traffic network.
(1) The traffic network is expressed, such that locations are represented as nodes, and a route between adjacent nodes is represented as a link. There is introduced a label consisting of the name of a link connecting the start node and a specific node and a cumulative cost from the start node to the specific node. During initial value setting, the start node is labeled with a temporary label (*, 0), and each of the remaining nodes is labeled with a temporary label ("PHgr", ∞), where xe2x80x9c*xe2x80x9d means that no link reaches the start node, xe2x80x9c"PHgr"xe2x80x9d means that no link has yet reached the corresponding node, and xe2x80x9c∞xe2x80x9d means a numerical value which is sufficiently large within the context of a relevant problem.
(2) Among nodes bearing temporary labels, a node having the lowest potential (i.e., cumulative cost) is selected. When the selected node is the target location, the route determination is ended, and the end processing routine described in (4) below is performed. When the selected node is not the target location, the processing routine described in (3) is performed successively.
(3) The potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated. When the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential value in the temporary label of the end node is replaced with the calculated potential value of the end node. The temporary label of the node having the lowest potential is rendered permanent, and the processing routine described in (2) above is executed.
(4) Permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
In the specification, the above-described label determination method will be referred to as a xe2x80x9cpotential-basis label determination method,xe2x80x9d in order to distinguish it from the conventional label determination method.
Next, a second aspect of the present invention will be described.
A computer is operated in order to determine a minimum-cost route from a start location to a target location between which a person walks from the start location to an entrance point (a station in the case of a railroad network) of a transportation network, uses the transportation network to an exit point (a station in the case of a railroad network) of the transportation network, and walks from the exit point of the transportation network to the target location. The method comprises the following steps:
(1) At least one entrance point of a transportation network to be used which incurs a cost within a predetermined range and at least one exit point of the transportation network which incurs a cost within the predetermined range are chosen. The cost of the route from the start location to the entrance point and the cost of the route from the exit point of the transportation network to the target location are calculated from a road map. The walking routes having calculated costs are incorporated, as links, into a traffic network comprising the transportation network. The above-described calculation will be referred to as a xe2x80x9croad-map-basis walking cost calculation.xe2x80x9d
(2) The traffic network is expressed, such that locations are represented as nodes, and a route between adjacent nodes is represented as a link. There is introduced a label consisting of the name of a link connecting the start node and a specific node and a cumulative cost from the start node to the specific node. During initial value setting, the start node is labeled with a temporary label (*, 0), and each of the remaining nodes is labeled with a temporary label ("PHgr", ∞), where xe2x80x9c*xe2x80x9d means that no link reaches the start node, xe2x80x9c"PHgr"xe2x80x9d means that no link has yet reached the corresponding node, and xe2x80x9c∞xe2x80x9d means a numerical value which is sufficiently large within the context of a relevant problem.
(3) Among nodes bearing temporary labels, a node having the lowest potential (i.e., cumulative cost) is selected. When the selected node is the target location, the route determination is ended, and the end processing routine described in (5) below is performed. When the selected node is not the target location, the processing routine described in (4) is performed successively.
(4) The potential of an end node which is linked from the node having the lowest potential and which has a temporary label is calculated. When the thus-calculated potential of the end node is lower than the potential indicated by the temporary label of the end node, the potential value in the temporary label of the end node is replaced with the calculated potential value of the end node. The temporary label of the node having the lowest potential is rendered permanent, and the processing routine described in (3) above is executed.
(5) Permanent labels are followed backward from the target location to the start location in order to determine a route of lowest potential, including walking routes.
In the first aspect of the present invention, the cost of a route from the start location to each entrance point of a transportation network to be used and the cost of a route from each exit point of the transportation network to the target location are each calculated on the basis of the corresponding straight-line distance. By contrast, in the second aspect of the invention, these costs are calculated accurately by use of a road map. When entrance and exits stations whose cost, calculated by the xe2x80x9croad-map-basis walking cost calculation,xe2x80x9d falls within a designated cost range are searched, a walking route from the start location to the entrance station and a walking route from the exit station to the target location are incorporated in the traffic network as links.
In the xe2x80x9croad-map-basis walking cost calculation,xe2x80x9d the same xe2x80x9cpotential-basis label determination methodxe2x80x9d as used in the first aspect is used. Since the network used here is a road network, the xe2x80x9cpotential-basis label determination methodxe2x80x9d is used after some modifications.
By use of the xe2x80x9cpotential-basis label determination method,xe2x80x9d a minimum-cost route is determined for the traffic network into which the links obtained through the xe2x80x9croad-map-basis walking cost calculationxe2x80x9d have been incorporated.
Next, the xe2x80x9cpotential-basis label determination methodxe2x80x9d will be described more specifically. In the potential-basis label determination method, the potential of each node is introduced into a corresponding label. A label for each node is defined as follows:
(1, p(v))
where 1 represents a link connecting adjacent nodes, v represents a node currently under consideration, and p(v) is the potential of node v. The potential p(v) represents a cumulative cost involved in a route from the start point to node v.
A route from the start location (start node) to a target location (target node) can be determined under the condition of minimizing cost.
[Process for Setting Initial Values]
The start node s is labeled with a temporary label (*, 0), and each of the remaining nodes is labeled with a temporary label ("PHgr", ∞), where xe2x80x9c*xe2x80x9d means that no link has yet reached the start node, xe2x80x9c"PHgr"xe2x80x9d means that no link has yet reached the corresponding node, and xe2x80x9c∞xe2x80x9d means a numerical value sufficiently large within the context of a relevant problem.
[Process for Searching a Lowest Potential Node]
Among nodes bearing temporary labels, a node having the lowest potential is searched, and is referred to as the lowest-potential node v. When the node searched here is the target node (target location), the node is labeled with a permanent label, and the processing proceeds to xe2x80x9cEnd process.xe2x80x9d In other cases, the processing proceeds to xe2x80x9cRoute determination process.xe2x80x9d
[Route Determination Process]
When a node connected to link a (outgoing link a) extending from node v is represented by
xcex4xe2x88x921a, and
the potential accumulated from the start node is represented by
p(V),
the potential of node xcex4xe2x88x921a is represented by
p(v)+d(a).
When p(v)+d(a) is smaller than p(xcex4xe2x88x921a) which is already set for node xcex4xe2x88x921a,
p(v)+d(a) is used as the new potential p(xcex4xe2x88x921a), and
the node is labeled with a temporary label (a, p(xcex4xe2x88x921a).
After the above-described processing is performed for all the links (outgoing links) extending from node v, the temporary label of node v is rendered permanent. Subsequently, the processing returns to the xe2x80x9cProcess for searching a lowest potential node.xe2x80x9d
[End Process]
Nodes which are obtained by the above-described processing and which each have a permanent label are output in a demanded form.
Next, the present invention will be described in more detail. FIG. 2 shows the relationship between nodes and links. Symbols used here have the following meanings.
v: node having the lowest potential among nodes bearing temporary labels;
u: node adjacent to node v;
a, b: links;
xcex4xe2x88x921a: node which link a reaches;
xcex4+1a: node from which link a extends;
d(a): cost involved in reaching link a; and
p(v): potential of node v (indicating cumulative cost from the start location (=xcexa3d(ai))).
As viewed from node v, a is an outgoing link, and b is an incoming link. As viewed from node u, a is an incoming link, and b is an outgoing link. d(a) is cost, such as time, distance, or money, which is incurred for using link a. Results to be obtained vary depending on the type of cost. Although generally d(a)=d(b) in a case as shown in FIG. 2(3), in some cases d(a)xe2x89xa0d(b). Potential p(v) is a sum of costs accumulated along a route from the start location 0 to node v.
A label of node u (same as xcex4xe2x88x921a, xcex4+1a) connected to node v via link a is defined as
(a, p(v)+d(a)) or
u (a, p(v)+d(a)).
Since p(v)+d(a) is p(u), the above label can be written as
(a, p(u)) or
u(a, p(u)).
That is, the label of node u is represented by link a connecting node u to node v, and a cumulative potential up to node u. A label which may be changed in the future is referred to as a xe2x80x9ctemporary label,xe2x80x9d and a label which will never be changed in the future is referred to as a xe2x80x9cpermanent label.xe2x80x9d That is, a permanent label for node u includes a lowest value of potential accumulated up to node u, because, in the present invention, a route starting from the start node is always determined, while nodes each having the lowest potential are selected. This concept will next be described.
Introduction of the concept of node potential simplifies program description and enables judgment as to whether processing is to end. As described above, the present invention utilizes the label determination method for route determination. FIG. 3 shows a set S of all nodes, as well as a set Sxe2x80x2 (hatched portion) of nodes bearing permanent labels. In order to find a route of lowest potential, a node bearing a label whose potential value is lowest is searched from nodes bearing temporary labels (=Sxe2x88x92Sxe2x80x2). Here, only outgoing links are considered, and it is assumed that the thus-searched node is node v. When nodes u1 and u2 are adjacent to node v, nodes u1 and u2 are labeled with temporary labels as follows (here, each of nodes u1 and u2 is assumed to be a node which has not yet been searched:
u1: (a1, p(v)+d(a1))
u2: (a2, p(v)+d(a2))
Subsequently, the temporary label (1, p(v)) of node v is rendered permanent, and node v is incorporated into the set Sxe2x80x2 of nodes bearing permanent labels. That the potential p(v) indicated by the label (1, p(v)) is the lowest can be proved as follows.
Suppose that node w is found next during the searching operation for searching a temporary label having the lowest potential value, and that node w is connected to adjacent nodes v, u2, and x via links b1, b2, and b3, respectively. In this case, temporary labels for nodes v, u2, and x are determined as follows:
v: (b1, p(w)+d(b1))
u2: (b2, p(w)+d(b2))
x: (b3, p(w)+d(b3))
The potential p(v) of node v indicated by the label (1, p(v)) rendered permanent satisfies the following relationship.
p(v)xe2x89xa6p(w)+d(b1)
This is because potential p(v) was selected during the preceding search in which node v was found, and therefore, p(v)xe2x89xa6p(w) stands. Accordingly, during a route determination performed for node w, selection of link b1 connecting node v and node w is not required. This also means that the permanent label (1, p(v)) of node v will not change. Thus, the potential p(v) is proved to be lowest.
Next, node u2 is considered. Node u2 has already been labeled with
(a2, p(v)+d(a2)).
The potential value of this label is compared with that of a new label
(b2, p(w)+d(b2)).
If p(v)+d(a2)xe2x89xa6p(w)+d(b2), the label of node u2 remains unchanged and the following label is maintained.
u2: (a2, p(v)+d(a2))
If p(v)+d(a2) greater than p(w)+d(b2), node u2 is labeled with the following temporary label.
u2: (b2, p(w)+d(b2))
Accordingly, through replacement of temporary labels, the route which produces the lowest potential is set.
As is understood from the above description, the corresponding lowest potential value is set into each permanent label, and presence of a temporary label represents the possibility of another route reducing the potential further.
The following programming technique is used to start route determination from a start node 0. That is, during initial value setting, start node 0 is labeled with a temporary label (*, 0), and each of the remaining nodes is labeled with a temporary label ("PHgr", ∞).
Therefore, in order to judge whether searching of a minimum-cost route including walking sections is ended, the computer checks whether xe2x80x9ca node corresponding to the target location has been labeled with a permanent label.xe2x80x9d The above-described operation can be performed by means of a program comprising the following steps.
Step 1 (Process for Setting Initial Values):
The start node is labeled with a temporary label (*, 0), and each of the remaining nodes is labeled with a temporary label ("PHgr", ∞).
Step 2 (Process for Searching the Node of the Lowest Potential):
Among nodes each bearing a temporary label, a node of lowest potential is searched and is regarded the lowest potential node v. When the searched node is a node corresponding to the target location, the processing proceeds to step S4 (End process). In other cases, the processing proceeds to step S3 (Route determination process).
Step 3 (Route Determination Process):
When node xcex4a adjacent to node v is connected to node v via link a, and a cost d(xcex4a) is involved in link a, the potential of node xcex4a is p(v)+d(a). In the case in which a potential p(xcex4a) has already been set to node ba, when p(v)+d(a) less than p(xcex4a), p(v)+d(a) is regarded a new potential p(xcex4a) in order to create a temporary label (a, p(xcex4a)). Subsequently, the temporary label of node v is rendered permanent. Subsequently, the processing returns to step 2 (Process for searching the node of lowest potential).
Step 4 (End Process)
Permanent labels are followed backward from node v in order to output the route in a demanded form.
FIG. 4 is a flowchart showing the above-described processing. The portion of processing other than process S xe2x80x9cwalking cost calculationxe2x80x9d in FIG. 4 corresponds to the xe2x80x9cpotential-basis label determination method.xe2x80x9d In FIG. 4, p(xcex4a) represents a potential already set for node xcex4a. When potential p(xcex4a) is greater than a newly calculated potential
p(v)+d(a),
p(xcex4a) in the label is replaced with
p(v)+d(a).
Further, the link name in the label is replaced with xe2x80x9ca,xe2x80x9d and node xcex4a is labeled with a new temporary label
(a, xcex4a).
When an adjacent node is searched, search operation is performed only for outgoing links. Since the flowchart of FIG. 4 has a xe2x80x9cDO WHILExe2x80x9d configuration, labeling of node v with a permanent label is performed in the end process in which the lowest potential node is searched and regarded node v. That is, in the above description, the labeling operation is described as being performed in step 2. However, in the flowchart, the labeling operation is incorporated in the processing in step 3. This is merely a matter in relation to programming, and no fundamental difference in concept is present therebetween.
The processing shown in FIG. 4 is common between the first and second aspect of the present invention. Therefore, when actual processing is performed in accordance with the first aspect of the present invention, xe2x80x9cstraight-line-distance-basis walking cost calculationxe2x80x9d is performed as the xe2x80x9ccalculation of walking cost,xe2x80x9d and when actual processing is performed in accordance with the second aspect of the present invention, xe2x80x9croad-map-basis walking cost calculationxe2x80x9d is performed as the xe2x80x9ccalculation of walking cost.xe2x80x9d The details of these calculations will be described in the xe2x80x9cEmbodiments of the Inventionxe2x80x9d section.
In the above-described route determination, the link table as shown in FIG. 5 is created. Therefore, through an operation of following nodes backward from the target location with reference to the link table as shown in FIG. 5 and link names set in permanent labels, a minimum-cost route extending from the start location to the target location bearing a permanent label can be found.